SP1812 LCS2 - Longest Common Substring II

我们可以思考一下如何用$\text{SAM}$求两个串的最长公共子串点这里。

多个字符串匹配也很简单，对于每个节点记录每个字符串能匹配的最大值的最小值。

求最大值就是求两个串的最长公共子串，只不过需要给父节点更新，每次取最小值就得到答案。

只不过为了保证先更新儿子，再更新父亲，我们需要用拓扑序实现。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define INF 0x3f3f3f3f

const int MAXN = 2 * 100000 , MAXC = 26;
struct Suffix_Automaton {
	int Size , Last , Root , Maxlen[ MAXN + 5 ];
	int Trans[ MAXN + 5 ][ MAXC + 5 ] , Link[ MAXN + 5 ];
	int Max[ MAXN + 5 ] , Min[ MAXN + 5 ];	
	int Sortlen[ MAXN + 5 ] , tot[ MAXN + 5 ];
	
	Suffix_Automaton( ) { Root = Size = Last = 1; }
	
	void Copy( int u , int v ) {
		for( int i = 1 ; i <= MAXC ; i ++ )
			Trans[ u ][ i ] = Trans[ v ][ i ];
	}
	void Extend( int chr ) {
		int Newnode = ++ Size , u = Last;
		Maxlen[ Newnode ] = Maxlen[ u ] + 1;
		
		for( ; u && !Trans[ u ][ chr ] ; u = Link[ u ] )
			Trans[ u ][ chr ] = Newnode;
		
		if( !u ) Link[ Newnode ] = Root;
		else {
			int v = Trans[ u ][ chr ];
			
			if( Maxlen[ v ] == Maxlen[ u ] + 1 ) Link[ Newnode ] = v;
			else {
				int w = ++ Size;
				Copy( w , v ); Maxlen[ w ] = Maxlen[ u ] + 1;
				for( ; u && Trans[ u ][ chr ] == v ; u = Link[ u ] ) Trans[ u ][ chr ] = w;
				Link[ w ] = Link[ v ];
				Link[ v ] = Link[ Newnode ] = w;
			}
		}
		Last = Newnode;
	}
	
	void Sort( ) {
		for( int i = 1 ; i <= Size ; i ++ ) tot[ Maxlen[ i ] ] ++;
		for( int i = 1 ; i <= Size ; i ++ ) tot[ i ] += tot[ i - 1 ];
		for( int i = 1 ; i <= Size ; i ++ ) Sortlen[ tot[ Maxlen[ i ] ] -- ] = i;
	}
	void Build( char *str ) {
		int len = strlen( str );
		for( int i = 0 ; i < len ; i ++ )
			Extend( str[ i ] - 'a' + 1 );
		Sort( );
		for( int i = 1 ; i <= Size ; i ++ ) Min[ i ] = INF;
	}

	void Work( char *str ) {
		int len = strlen( str );
		int u = Root , cnt = 0;
		for( int i = 0 ; i < len ; i ++ ) {
			int ch = str[ i ] - 'a' + 1;
			for( ; u && !Trans[ u ][ ch ] ; u = Link[ u ] ) cnt = Maxlen[ Link[ u ] ]; 
			if( u ) {
				u = Trans[ u ][ ch ];
				Max[ u ] = max( Max[ u ] , ++ cnt );
			}
			else	
				u = Root , cnt = 0;
		}
		
		for( int i = Size ; i >= 1 ; i -- ) {
			int u = Sortlen[ i ] , Fa = Link[ u ];
			Max[ Fa ] = max( Max[ Fa ] , min( Maxlen[ Fa ] , Max[ u ] ) );
			Min[ u ] = min( Min[ u ] , Max[ u ] ); Max[ u ] = 0;
		}
	}
}SAM;

int n , Ans;
char str[ 11 ][ MAXN + 5 ];
int main( ) {
	for( n = 1 ; ~scanf("%s",str[ n ]) ; n ++ ); n --;
	SAM.Build( str[ 1 ] ); 
	for( int i = 2 ; i <= n ; i ++ ) SAM.Work( str[ i ] );
	
	for( int i = 1 ; i <= SAM.Size ; i ++ )
		Ans = max( Ans , SAM.Min[ i ] );
	printf("%d",Ans);
	return 0;
}